package com.lee.algorithm.tree;

import com.lee.algorithm.tree.struct.TreeNode;

import java.util.LinkedList;
import java.util.Queue;

/***
 * @description: 完全二叉树
 *      除了最后一层之外的其他每一层都被完全填充，并且所有结点都保持向左对齐
 * @author : 青石路
 * @date: 2021/12/6 9:03
 */
public class CompleteBinaryTree {

    /**
     * 宽度遍历
     * 1) 任一节点，有右无左，直接返回false
     * 2) 在 1) 不违规的情况下，如果遇到了第一个左右孩子不全的节点，该节点之后的节点都是叶子节点，否则返回false
     * @param head
     * @return
     */
    public static boolean isCBT(TreeNode<Integer> head) {

        if (head != null) {
            Queue<TreeNode<Integer>> queue = new LinkedList<>();
            TreeNode<Integer> cur = head;
            queue.add(cur);
            boolean isAllLeaf = false;
            while (!queue.isEmpty()) {
                cur = queue.poll();
                if (isAllLeaf && (cur.left != null || cur.right != null)) {     // 2) 的实现
                    return false;
                }
                if (cur.right != null && cur.left == null) {                    // 1) 的实现
                    return false;
                }
                if ((cur.left == null || cur.right == null) && !isAllLeaf) {
                    isAllLeaf = true;
                }

                if (cur.left != null) {
                    queue.add(cur.left);
                }
                if (cur.right != null) {
                    queue.add(cur.right);
                }
            }
        }
        return true;
    }

    public static void main(String[] args) {

        TreeNode<Integer> head = new TreeNode<>(1);
        TreeNode<Integer> headL = new TreeNode<>(7);
        TreeNode<Integer> headR = new TreeNode<>(3);
        head.left = headL;
        head.right = headR;

        TreeNode<Integer> thirdLevel1 = new TreeNode<>(6);
        TreeNode<Integer> thirdLevel2 = new TreeNode<>(5);
        TreeNode<Integer> thirdLevel3 = new TreeNode<>(4);

        headL.right = thirdLevel1;
        headL.left = thirdLevel2;
        headR.left = thirdLevel3;

        boolean cbt = isCBT(head);
        System.out.println("是否是完全二叉树：" + cbt);
    }
}
